﻿using System;

namespace DataStructures.List
{
    public class LinkedList<E> : AbstractList<E>
    {
        protected LinkedListNode<E> first;
        public override int Size
        {
            get
            {
                int size = 0;
                for (LinkedListNode<E> node = first; node != null; node = node.Next)
                {
                    ++size;
                }
                return size;
            }
        }

        protected override void checkEmpty()
        {
            if (null == first)
            {
                throw new EmptyListException(
                    "Trying to access elements from an empty list",
                    new IndexOutOfRangeException("The size of the list is not larger than the index"));
            }
        }

        public override E getFirst()
        {
            checkEmpty();
            return first.Element;
        }

        protected LinkedListNode<E> getLastNode()
        {
            checkEmpty();
            LinkedListNode<E> node;
            for (node = first; null != node.Next; node = node.Next) ;
            return node;
        }
        public override E getLast()
        {
            return getLastNode().Element;
        }

        protected LinkedListNode<E> getNodeByIndex(int index)
        {
            checkIndexMin(index);
            checkEmpty();
            LinkedListNode<E> node = first;
            for (int i = 0; i < index && node != null; ++i) node = node.Next;
            if (null == node) throw new IndexOutOfRangeException("The size of the list is not larger than the index");
            return node;
        }
        public override E getByIndex(int index)
        {
            return getNodeByIndex(index).Element;
        }

        public override bool insertBeforeFirst(E element)
        {
            first = new LinkedListNode<E>(element, first);
            return true;
        }
        public override bool insertAfterLast(E element)
        {
            if (null == first) return insertBeforeFirst(element);
            LinkedListNode<E> node;
            for (node = first; null != node.Next; node = node.Next) ;
            node.Next = new LinkedListNode<E>(element);
            return true;
        }

        public override bool insertByIndex(int index, E element)
        {
            checkIndexMin(index);
            if (0 == index) return insertBeforeFirst(element);

            LinkedListNode<E> node = first;
            for (int i = 1; i < index && node != null; ++i) node = node.Next;
            if (node == null) throw new IndexOutOfRangeException();
            node.Next = new LinkedListNode<E>(element, node.Next);
            return true;
        }

        public override E removeFirst()
        {
            checkEmpty();
            E temp = first.Element;
            first = first.Next;
            return temp;
        }
        public override E removeLast()
        {
            checkEmpty();
            if (null == first.Next) return removeFirst();
            LinkedListNode<E> node1, node2;
            for (node1 = first, node2 = first.Next; null != node2.Next; node2 = node2.Next) node1 = node2;
            node1.Next = null;
            return node2.Element;
        }
        public override E removeByIndex(int index)
        {
            checkIndexMin(index);
            if (0 == index) return removeFirst();
            LinkedListNode<E> node = first;
            for (int i = 1; i < index && node.Next != null; ++i) node = node.Next;
            if (node.Next == null) throw new IndexOutOfRangeException();
            E temp = node.Next.Element;
            node.Next = node.Next.Next;
            return temp;
        }

        public override bool setFirst(E element)
        {
            checkEmpty();
            first.Element = element;
            return true;
        }
        public override bool setLast(E element)
        {
            getLastNode().Element = element;
            return true;
        }
        public override bool setByIndex(int index, E element)
        {
            getNodeByIndex(index).Element = element;
            return true;
        }

        public override int indexOf(E element)
        {
            int result = 0;
            for (LinkedListNode<E> node = first; null != node; node = node.Next, ++result)
            {
                if (node.Element.Equals(element)) return result;
            }
            return -1;
        }
        public override int lastIndexOf(E element)
        {
            int result = -1, index = 0;
            for (LinkedListNode<E> node = first; null != node; node = node.Next, ++index)
            {
                if (node.Element.Equals(element)) result = index;
            }
            return result;
        }
        public override bool hasElement(E element)
        {
            return indexOf(element) >= 0;
        }

        protected class LinkekListIterator<E> : IIterator<E>
        {
            LinkedListNode<E> currentNode;

            public LinkekListIterator(LinkedListNode<E> firstNode)
            {
                currentNode = firstNode;
            }

            public bool hasNext()
            {
                return currentNode != null;
            }

            public E next()
            {
                E temp = currentNode.Element;
                currentNode = currentNode.Next;
                return temp;
            }
        }
        public override IIterator<E> getIterator()
        {
            return new LinkekListIterator<E>(first);
        }

    }
}
